
# -*- coding: utf-8 *-*
'''
@author: Geraldo Oliveira
@date: 13 de abril de 2013
@obs: 
Algoritmo de ordenacao ShellSort
origem:
http://pt.wikipedia.org/wiki/Shell_sort#C.C3.B3digo_em_Python
'''

class ShellSort(object):
	
	def __init__(self, lista):
		'''
		Recebe a lista a ordenar

			lista  -> Lista a ordenar
		'''
		self.lista = lista

	def run(self):
		'''	
		Algoritmo ShellSort 
		'''
		n = len(self.lista)
		h = int(n / 2)
		while h > 0:
			for i in range(h, n):
				c = self.lista[i]
				j = i
				while j >= h and c < self.lista[j - h]:
					self.lista[j] = self.lista[j - h]
					j = j - h
					self.lista[j] = c
			h = int(h / 2.2)
	
	def nome(self):
		'''
		Devolve o nome do metodo de ordenacao
		'''
		return "shellsort"
	
	def o(self, n):
		'''
		Calculo do valor teorico

		Recebe:
			n 	-> numero de elementos
		'''
		return n**2

	def __str__(self):
		'''
		Imprime o objecto 
		'''
		return str(self.lista)
